package leetcode每日一题;

import java.util.Stack;

/**
 * 1. 问题描述
 *      请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，
 *      至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用0 来代替。
 *
 *      例如，给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
 *      你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]。
 *
 * 2. 算法分析
 *      单调栈的应用
 *         1. 什么是单调栈
 *             所谓的单调栈，其本质还是一个栈，只不过这个栈中元素按照一定的升序或者降序排列
 *             一般我们用出栈顺序来定义单调栈
 *             具体的例子：
 *                 [4,2,1] 当前入栈为元素为5
 *                 此时就是一个单调栈，进栈为4，2，1，出栈为1，2，4(元素按照单调增的顺序依次出栈)
 *                 为了维护栈的单调性，如果当前入栈元素破坏了栈的单调性，我们需要对栈进行调整，即如
 *                 果当前进栈元素大于栈顶，让栈顶出栈，依次比较知道当前元素小于此时的栈顶元素，将当
 *                 前入栈元素作为新的栈顶元素
 *
 *         2. 单调栈的性质
 *             注意：我们定义左边表示先于当前元素之前入栈的元素，右边表示栈顶元素之后入栈的元素
 *             1. 栈顶元素的左边都是比栈顶大的元素，即当前栈的长度-1就是栈顶元素左边比栈顶元素
 *                大的元素个数
 *             2. 如果说当前入栈元素大于当前栈顶元素，此时实际上破坏了单调栈的单调性，所以我们
 *                需要进行调整，并且当前元素是整个数据元素中栈顶元素右边第一个比栈顶元素大的元
 *                素
 *             具体还是上述的为例子 [4,2,1] 当前入栈元素为5
 *             1的左边比1小的元素只有[2,4],当前入栈的5是1右边第一个比栈顶元素大的元素
 *
 *         应用：
 *             对于此题而言，我们需要从T中找到第i个元素的右边第一个大于第i个元素的索引，显然我们根据
 *             单调栈的性质，很快可以确定此题可以使用单调栈来完成
 *
 *             当然也可以使用双重for循环，但是此时的时间复杂度比较高 最坏时间复杂度为O(n^2),不推荐
 *                 int len = T.length;
 *                 int[] ans = new int[len]; // 创建一个存放结果的数组
 *                 for(int i = 0; i < len; i++) {
 *                     if(i == len -1) {
 *                         ans[i] = 0;
 *                     }
 *                     for(int j = i; j < len; j++) {
 *                         if(T[j] > T[i]) {
 *                             ans[i] = j - i;
 *                             break;
 *                         }
 *                     }
 *                 }
 *                 return ans;
 *
 *             下面我们利用单调栈来用线性时间内解决此问题
 *
 *     具体分析下述问题：
 *          根据单调栈的特点：当入栈的元素大于栈顶元素时，此时入栈元素就是栈顶元素在原有
 *          数据集合中右边第一个大于该元素的值(即当前入栈元素的索引-栈顶元素的索引就是以
 *          栈顶元素为起点，其右边第一个比它大的位置)
 *
 *          下面我们以一个具体的案例来说明上述单调栈的具体实现过程：
 *           T = {73, 74, 75, 71, 69, 72, 76, 73}   stack：单调栈
 *           ans = [0 ,0 ,0 ,0, 0, 0, 0]
 *              i = 0   stack = {}  ans = [0,0,0,0,0,0,0]
 *              stack = {(0,73)}  此时栈空，将当前元素入栈
 *
 *              i = 1    stack = {(0,73)}  ans = [0,0,0,0,0,0,0]
 *              此时T[1] > top.temp   ans[top.id] = i - top.id
 *              ans[0] = 1 - 0 = 1 ---> ans = [1,0,0,0,0,0,0]
 *
 *              i = 2    stack = {(1,74)}  ans = [1,0,0,0,0,0,0]
 *              此时T[2] > top.temp   ans[top.id] = i - top.id
 *              ans[1] = 2 - 1 = 1 ---> ans = [1,1,0,0,0,0,0]
 *
 *              i = 3,4    stack = {(2,75)}  ans = [1,1,0,0,0,0,0]
 *              此时T[3] < top.temp  此时直接进栈(因为不改变单调栈的特点)
 *              stack = {(2,75),(3,71),(4,69)}
 *
 *              i = 5 stack = {(2,75),(3,71),(4,69)} ans = [1,1,0,0,0,0,0]
 *              此时T[5] > top.temp  开始让栈顶元素出栈：
 *                  ans[top.id] = i - top.id  ans[4] = 5 - 4 = 1
 *                  stack.pop()
 *                  ans[top.id] = i - top.id  ans[3] = 5 - 3 = 2
 *                  stack.pop()
 *
 *              i = 6,7省略
 *
 *      关于单调栈的定义实际上并不难，但是我们需要根据具体的题目能够反应出当前问题是否可以利用单调栈来解决
 *      我们需要牢记单调栈的特点，根据其特点从题目背景中找到突破口
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 每日温度 {

    /*定义一个结构体*/
    static class Temperature {
        int id; // 索引
        int temp; // 温度

        public Temperature(int id, int temp) {
            this.id = id;
            this.temp = temp;
        }
    }


    public static void main(String[] args) {
        /*int[] T = {73, 74, 75, 71, 69, 72, 76, 73};
        for (int i : dailyTemperatures(T)) {
            System.out.print(i+" ");
        }*/
        System.out.println(Math.ceil(Math.sqrt(5)));
    }
    public static int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] ans = new int[len];
        Stack<Temperature> stack = new Stack<>();
        Temperature temperature = null;
        for (int i = 0; i < len; i++) {
             temperature = new Temperature(i,T[i]);
             while (!stack.empty() && stack.peek().temp < T[i]) {
                 ans[stack.peek().id] = i - stack.peek().id;
                 stack.pop();
             }
             stack.add(temperature);
        }
        return ans;
    }
}
